package com.mgq.algorithm.dabiaofa;

import java.util.Random;

/**
 * 染色问题
 * 左边是绿色, 右边是红色
 * 给一个 s= "RGRGGRR"
 * 染色过程
 *           RGRGGRR(全是右边, 3次)
 * R GRGGRR  G  RRRRRR  4次
 * RG RGGRR  GG RRRRR  3次
 * RGR GGRR  GGG RRRR  4次
 * RGRG GRR  GGGG RRR  3次
 * RGRGG RR  GGGGG RR  2次
 * RGRGGR R  GGGGGG R  3次
 * RGRGGRR   GGGGGGG   4次  //全是左边
 * 最小是2
 */
public class GreenRed {
    public static int greenRed(String s) {
        char[] chars = s.toCharArray();
        int N= chars.length;
        int min=0;
        int count1=0;
        //左边部分从0开始, 右边部分就是N-L
        for (int L = 0; L <= N; L++) {
            if (L == 0) {
                int count=0;
                //全是右边,统计有多个G,全部变为R
                for (int i = 0; i < N; i++) {
                    if (chars[i] == 'G') {
                        count++;
                    }
                }
                min= count;
            } else if (L == N) {
                //全部是左边,统计有多个R,全部变为G
                for (int i = 0; i < N; i++) {
                    if (chars[i] == 'R') {
                        count1++;
                    }
                }
            } else {
                //统计array[0-L] 共有多少个R,变为G + array[L+1,N-1]有多个G,全部变为R
                int left=0;
                int right=0;
                for (int i = 0; i < L; i++) {
                    if (chars[i] == 'R') {
                        left++;
                    }
                }
                for (int i = L; i < N; i++) {
                    if (chars[i] == 'G') {
                        right++;
                    }
                }
                int  count2 = left + right;
                min = Math.min(min, count2);
            }
        }
        return Math.min(min, count1);
    }

    /**
     * 使用预处理结构,来加速.方法一的问题是每次都需要遍历去查询有几个R和几个G.
     * 使用辅助数组中,可以直接取到答案.可以起到加速的作用
     * @param s
     * @return
     */
    public static int greenRed2(String s) {
        if (s.length()==0) return 0;
        //使用数组加速
        char[] chars = s.toCharArray();
        int N = chars.length;
        //left保存的是从左右往,依次有多少个R
        int[] rArray = new int[N];
        int[] gArray = new int[N];
        int count=0;
        for (int i = 0; i <N; i++) {
            if (chars[i] == 'R') {
                count++;
            }
            rArray[i]=count;
        }
        count=0;
        for (int j = N-1; j >=0 ; j--) {
            if (chars[j] == 'G') {
                count++;
            }
            gArray[j]=count;
        }
        //---------
        //左边部分从0开始, 右边部分就是N-L
        int min=0;
        int count2=0;
        for (int L = 0; L <= N; L++) {
            if (L == 0) {
                //全是右边,统计有多个G,全部变为R
                min = gArray[0];
            } else if (L == N) {
                //全部是左边,统计有多个R,全部变为G
                 count2 = rArray[N - 1];
            } else {
                //统计array[0-L] 共有多少个R,变为G + array[L+1,N-1]有多个G,全部变为R
                int count3 = rArray[L-1] + gArray[L];
                min = Math.min(min, count3);
            }
        }
        return Math.min(min, count2);
    }
    public static void main(String[] args) {
        /*greenRed("RGRGGRR");

        System.out.println(greenRed("RGRGGRR"));
        greenRed2("RGRGGRR");
        System.out.println();*/
        for (int i = 0; i < 100000; i++) {
            String s = generatorRandom();
            if (greenRed(s)!=greenRed2(s)) {
                System.out.println("error");
            }
        }

    }

    public static String generatorRandom() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < new Random().nextInt(10); i++) {
            s.append("G");
            for (int j = 0; j < new Random().nextInt(10); j++) {
                s.append("R");
            }
        }
        return s.toString();
    }
}
